Symmetric tree

Time: O(N); Space: O(H); easy

Note:

• H is height of binary tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Example 1:

Symmetric binary tree [1,2,2,3,4,4,3]

    1
   / \
  2   2
 / \ / \
3  4 4  3

Example 2:

Non symmetric binary tree [1,2,2,null,3,null,3]

  1
 / \
2   2
\    \
 3    3

Follow up:

Solve it both recursively and iteratively.

class TreeNode:
    '''
    Definition for a binary tree node
    '''
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Recursive solution

A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

Push an element in stack

Therefore, the question is: when are two trees a mirror reflection of each other?

Two trees are a mirror reflection of each other if:

1. Their two roots have the same value.

2. The right subtree of each tree is a mirror reflection of the left subtree of the other tree.

Push an element in stack

This is like a person looking at a mirror. The reflection in the mirror has the same head, but the reflection’s right arm corresponds to the actual person’s left arm, and vice versa.

The explanation above translates naturally to a recursive function as follows.

class Solution1(object):
    """
    Time: O(n). Because we traverse the entire input tree once, the total run time is O(n),
          where nn is the total number of nodes in the tree.
    Space: The number of recursive calls is bound by the height of the tree.
           In the worst case, the tree is linear and the height is in O(n).
           Therefore, space complexity due to recursive calls on the stack is O(n) in the worst case.
    """

    def isSymmetricRecu(self, left, right):
        if left is None and right is None:
            return True
        if left is None or right is None or left.val != right.val:
            return False
        return self.isSymmetricRecu(left.left, right.right) and self.isSymmetricRecu(left.right, right.left)

    def isSymmetric(self, root):
        '''
        :type root: TreeNode
        :rtype: bool
        '''
        if root is None:
            return True

        return self.isSymmetricRecu(root.left, root.right)

s = Solution1()
root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(2)
root.left.left, root.right.right = TreeNode(3), TreeNode(3)
root.left.right, root.right.left = TreeNode(4), TreeNode(4)
assert s.isSymmetric(root) == True

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(2)
root.left.right, root.right.right = TreeNode(3), TreeNode(3)
assert s.isSymmetric(root) == False

2. Iterative solution

Instead of recursion, we can also use iteration with the aid of a queue.

Each two consecutive nodes in the queue should be equal, and their subtrees a mirror of each other.

Initially, the queue contains root and root.

Then the algorithm works similarly to BFS, with some key differences.

Each time, two nodes are extracted and their values compared.

Then, the right and left children of the two nodes are inserted in the queue in opposite order.

The algorithm is done when either the queue is empty, or we detect that the tree is not symmetric (i.e. we pull out two consecutive nodes from the queue that are unequal).

class Solution2(object):
    """
    Time: O(n). Because we traverse the entire input tree once, the total run time is O(n),
          where nn is the total number of nodes in the tree.
    Space: There is additional space required for the search queue.
           In the worst case, we have to insert O(n) nodes in the queue.
           Therefore, space complexity is O(n).
    """
    def isSymmetric(self, root):
        '''
        :type root: TreeNode
        :rtype: bool
        '''
        if root is None:
            return True
        stack = []
        stack.append(root.left)
        stack.append(root.right)

        while stack:
            p, q = stack.pop(), stack.pop()

            if p is None and q is None:
                continue

            if p is None or q is None or p.val != q.val:
                return False

            stack.append(p.left)
            stack.append(q.right)

            stack.append(p.right)
            stack.append(q.left)

        return True

s = Solution2()
root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(2)
root.left.left, root.right.right = TreeNode(3), TreeNode(3)
root.left.right, root.right.left = TreeNode(4), TreeNode(4)
assert s.isSymmetric(root) == True

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(2)
root.left.right, root.right.right = TreeNode(3), TreeNode(3)
assert s.isSymmetric(root) == False

See also:

https://leetcode.com/problems/symmetric-tree